﻿#pragma once
#include<iostream>

using namespace std;

template<class K,class V>
struct AVLTreeNode
{
	AVLTreeNode(const K& key, const V& val)
		:_val(val),
		_key(key),
		_left(nullptr),
		_right(nullptr),
		_parent(nullptr),
		_bf(0)
	{}

	bool is_leaf()
	{
		if (_left || _right)
			return false;

		return true;
	}

	K _key;
	V _val;
	AVLTreeNode* _left;
	AVLTreeNode* _right;
	AVLTreeNode* _parent;
	int _bf;
};

template<class K,class V>
class AVLTree
{
public:
	typedef AVLTreeNode<K, V> Node;
	enum direction
	{
		LEFT,
		RIGHT
	};

	AVLTree()
		:_root(nullptr)
	{}

	~AVLTree()
	{
		_Destroy(_root);
	}

	bool insert(const K& key,const V& val)
	{
		if (_root == nullptr)
		{
			_root = new Node(key, val);
			return true;
		}

		Node* parent = _root;
		Node* cur = _root;
		direction dir;

		while (cur)
		{
			if (key == cur->_key)
				return false;
			else if (key < cur->_key)
			{
				dir = LEFT;
				parent = cur;
				cur = cur->_left;
			}
			else if (key > cur->_key)
			{
				dir = RIGHT;
				parent = cur;
				cur = cur->_right;
			}
		}

		cur = new Node(key, val);
		cur->_parent = parent;
		if (dir == LEFT)
			parent->_left = cur;
		else if (dir == RIGHT)
			parent->_right = cur;

		while (parent)
		{
			//修改平衡因子
			if (cur == parent->_left)
				parent->_bf--;
			else if (cur == parent->_right)
				parent->_bf++;

			//判断平衡因子
			if (parent->_bf == 0)
				break;
			else if (parent->_bf == 1 || parent->_bf == -1)
			{
				cur = parent;
				parent = parent->_parent;
			}
			else
			{
				if (parent->_bf == 2)
				{
					if (cur->_bf == 1)
					{
						RotateL(parent);
					}
					else if (cur->_bf == -1)
					{
						RotateRL(parent);
					}
				}
				else if (parent->_bf == -2)
				{
					if (cur->_bf == -1)
					{
						RotateR(parent);
					}
					else if (cur->_bf == 1)
					{
						RotateLR(parent);
					}
				}
				break;
			}
		}
	}

	bool is_balance()
	{
		return _is_blance(_root);
	}

	void Inorder()
	{
		_Inorder(_root);
		cout << endl;
	}
private:
	Node* _root;

	void _Destroy(Node* root)
	{
		if (root == nullptr)
			return;

		_Destroy(root->_left);
		_Destroy(root->_right);

		delete root;
	}

	void RotateR(Node* root)
	{
		Node* grandparent = root->_parent;
		Node* parent = root;
		Node* cur = root->_left;
		//Node* childL = cur->_left;
		Node* childR = cur->_right;

		if (grandparent)
		{
			if (grandparent->_left == root)
			{
				grandparent->_left = cur;
			}
			else if (grandparent->_right == root)
			{
				grandparent->_right = cur;
			}
		}
		else
		{
			_root = cur;
		}
		
		cur->_parent = grandparent;
		cur->_right = parent;
		
		parent->_parent = cur;
		parent->_left = childR;

		if(childR)
			childR->_parent = parent;

		parent->_bf = cur->_bf = 0;
	}

	void RotateL(Node* root)
	{
		Node* grandparent = root->_parent;
		Node* parent = root;
		Node* cur = root->_right;
		Node* childL = cur->_left;
		//Node* childR = cur->_right;

		if (grandparent)
		{
			if (grandparent->_left == root)
			{
				grandparent->_left = cur;
			}
			else if (grandparent->_right == root)
			{
				grandparent->_right = cur;
			}
		}
		else
		{
			_root = cur;
		}

		cur->_parent = grandparent;
		cur->_left = parent;

		parent->_parent = cur;
		parent->_right = childL;

		if(childL)
			childL->_parent = parent;

		parent->_bf = cur->_bf = 0;
	}

	void RotateLR(Node* root)
	{
		Node* parent = root;
		Node* cur = root->_left;
		Node* child = cur->_right;
		int bf = child->_bf;

		RotateL(cur);
		RotateR(parent);

		if (bf == 0)
		{
			parent->_bf = cur->_bf = child->_bf = 0;
		}
		else if (bf == 1)
		{
			cur->_bf = -1;
			child->_bf = parent->_bf = 0;
		}
		else if (bf == -1)
		{
			parent->_bf = 1;
			child->_bf = cur->_bf = 0;
		}
	}

	void RotateRL(Node* root)
	{
		Node* parent = root;
		Node* cur = root->_right;
		Node* child = cur->_left;
		int bf = child->_bf;

		RotateR(cur);
		RotateL(parent);

		if (bf == 0)
		{
			parent->_bf = cur->_bf = child->_bf = 0;
		}
		else if (bf == 1)
		{
			parent->_bf = -1;
			cur->_bf = child->_bf = 0;
		}
		else if (bf == -1)
		{
			cur->_bf = 1;
			parent->_bf = child->_bf = 0;
		}
	}

	void _Inorder(Node* root)
	{
		if (root == nullptr)
			return;

		_Inorder(root->_left);
		cout << root->_key << ' ';
		_Inorder(root->_right);
	}

	size_t Height(Node* root)
	{
		if (root == nullptr)
			return 0;

		size_t left = Height(root->_left);
		size_t right = Height(root->_right);

		return max(left, right) + 1;
	}

	bool _is_blance(Node* root)
	{
		if (root == nullptr)
			return true;

		size_t left = Height(root->_left);
		size_t right = Height(root->_right);

		return ((left - right <= 1) || (left - right >= -1)) && _is_blance(root->_left) && _is_blance(root->_right);
	}
};